In any network in which multiple users are connected to a shared communications channel, there is typically a method to resolve which user obtains use of the channel when there is contention. When two or more users attempt to transmit data simultaneously in the same bandwidth, a collision can occur and data can be lost. The various methods to resolve contests between users and to recover from data collisions are often called Medium Access Control (MAC) protocols.
A major category of MAC protocols is the random access type. These protocols adopt package contention techniques, such as Slotted ALOHA or Carrier Sense Multiple Access (CSMA) to handle channel contention. Slotted Aloha reduces the number of data collisions by dividing the channel into time slots and requiring that users transmit at the beginning of each slot. Collisions occur in Slotted Aloha systems when two or more users transmit to the same time slot simultaneously. CSMA reduces collisions by having users monitor the data channels to determine whether the channel is busy or available for transmission. Collisions occur in CSMA when two or more users simultaneously sense a channel is free and transmit at the same time.
A separate category of MAC protocols is the demand-assignment type. These protocols manage network contention by dividing the channel into reservation slots and requiring that users reserve a channel slot to transmit. Unlike the random access protocols, users on a demand-assignment system are assured that the data will transmit without collision once a successful reservation is made. Demand-assignment collisions still occur, however, in the reservation phase of the transmission when two or more users attempt to make reservations in the same bandwidth simultaneously.
Data collisions are a fact of life when multiple users are connected to a shared communications channel, regardless of whether a random access or demand assignment protocol is used. To avoid losing data every time a collision occurs, MAC protocols use collision resolution or back-off algorithms to recover from the collision and determine when to re-transmit the data that collided.
There are three widely-known types of back-off algorithms in the art. The first is a splitting algorithm, also known as a tree algorithm. The second type is an adaptive p-persistence algorithm, and the third is a binary exponential back-off (BEB) algorithm. Each algorithm takes a different approach to determine when to re-transmit data that previously collided.
No single standard exists to determine which of the three categories of back-off algorithms is best. One standard of performance is throughput. In general, throughput is the amount of data transferred from one user to another user in a specified amount of time. In contention resolution algorithms, throughput is often measured as a ratio of the number of successful transmissions to the total number of transmission opportunities. In a wireless internet access system that uses a demand-assignment protocol, for example, throughput is the ratio of the number of successful reservations made to the total number of reservation slots available.
Of the three aforementioned classes of back-off algorithms, tree algorithms generally have the highest throughput. Although their maximum stable throughput remains unknown, tree algorithms have achieved throughputs of 0.4878. However, this higher throughput comes with a price. The tree algorithm is by far the most sophisticated of the three back-off algorithms to implement and the number of networks that can implement a tree algorithm is limited because the algorithm requires that the users have full knowledge of the three possible conditions (success, collision, idle) for every reservation slot.
The second type of back-off algorithm is an adaptive p-persistence algorithm. An adaptive p-persistence algorithm operates by calculating a retransmission probability p determined by estimating the number of active users (users who are competing for the bandwidth) using feedback from the reservation slots. The algorithm increases p when an idle slot occurs and decreases p when a collision is detected. When there are infinite number of users in the system, the maximum achievable throughput of adaptive p-persistence algorithms is at most 1/e=0.3679. Under such circumstances, idles occur with a probability of 1/e˜0.3679, and collisions occur with a probability of 1−2/e˜0.2642.
As with a tree algorithm, an adaptive p-persistence algorithm requires feedback about the data channels that many networks do not provide. In many systems, including many computer and wireless communication networks, individual users know whether or not their own packets transmit successfully, but have no information about the status of other channels in the network. Because so many multi-user systems (including Ethernet, CATV and wireless networks) do not provide the requisite channel feedback, the BEB algorithm is often adopted for collision resolution.
Unlike tree and adaptive p-persistence algorithms, a BEB algorithm does not require that users provide feedback about every data channel. BEB operates as follows: an immediate first transmission is made as soon as a packet arrives at the head of the transmit queue. If the transmitting user detects a collision, it re-transmits k slots later, where k is a random integer number uniformly distributed over the interval [1, 2i]. The interval over which the uniformly distributed number is drawn is hereafter referred to as the back-off window. If i (the number of collisions) is greater than 16, the packet is lost and dropped. Once a packet is either transmitted successfully or is dropped, i is reset to zero. The logic that underlies BEB is that, for a given packet, a high number of unsuccessful transmissions implies that more users are contending for the available bandwidth and a larger Back-off window should be opened.
One of the downsides of BEB is that it suffers from a couple of performance problems. First, it causes the network to become unstable as the number of users grows very large. That is, as the number of users on a system approaches infinity the throughput of a BEB system approaches zero. In addition, BEB results in a last-come-first-serve effect among the competing users. Specifically, a user that has a packet newly arrived at the head of the transmit queue has a higher probability of acquiring a reservation slot than does a user that has already been in the queue and experienced one or more collisions. This occurs because the user whose packet just arrived in the queue will have a relatively smaller back-off window than the user that has already experienced several collisions. This is called the capture effect because it allows a single or a few winning users to dominate the available bandwidth.
Thus, an unsatisfied need exists in the industry for an improved method for resolving data collisions that overcomes deficiencies in the prior art, some of which are discussed above.